package datastructure.structure;


import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.function.Consumer;

/**
 * 最简单的树
 *
 * @author or2
 * @Description 最普通的树
 * @create 2021年09月05日 时间: 10:39
 */
public class SimpleTree<E extends Comparable<E>> {

    /**
     * 树的根节点
     */
    private Node root;
    private Class<E> clazz;

    public SimpleTree(Class<E> clazz) {
        this.clazz = clazz;
    }

    public SimpleTree<E> getTreeByPreAndInOrder(E[] preOrder, E[] inOrder) {
        if (preOrder.length == 0) {
            return null;
        }

        this.root = reConstructBinaryTree(preOrder, inOrder);
        return this;
    }

    /**
     * 根据<span color="green">前序遍历</span>与<span color="green">中序遍历</span>构建二叉树
     *
     * @param preOrder 前序遍历数组
     * @param inOrder  中序遍历数组
     * @return 所构建树的根节点
     */
    private Node reConstructBinaryTree(E[] preOrder, E[] inOrder) {
//        当前子树根节点
        Node root = new Node(preOrder[0]);
        if (preOrder.length == 1) {
            return root;
        }

        int preInInIndex = 0;
//        查找其在 中序中的下标
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == preOrder[0]) {
                preInInIndex = i;
                break;
            }
        }
//        若其含有左子树
        if (preInInIndex > 0) {
//            左子树前序
//            E[] leftPre = (E[]) new Object[preInInIndex];
            E[] leftPre = (E[]) Array.newInstance(clazz, preInInIndex);
            for (int i = 0; i < preInInIndex; i++) {
                leftPre[i] = preOrder[i + 1];
            }
//            左子树中序
//            E[] leftIn = (E[]) new Object[preInInIndex];
            E[] leftIn = (E[]) Array.newInstance(clazz, preInInIndex);
            for (int i = 0; i < preInInIndex; i++) {
                leftIn[i] = inOrder[i];
            }
//            左子树递归
            root.lChild = reConstructBinaryTree(leftPre, leftIn);
        }
//        若其含有右子树
        if (preOrder.length - preInInIndex - 1 > 0) {
            //右子树的先序,长度为 总-根-左子树
            int rIndex = preInInIndex + 1;
            int len = preOrder.length - rIndex;
            E[] rightPre = (E[]) Array.newInstance(clazz, len);
            //右子树的中序
            E[] rightIn = (E[]) Array.newInstance(clazz, len);
            for (int j = 0; j < len; j++) {
                rightIn[j] = inOrder[j + rIndex];
                rightPre[j] = preOrder[j + rIndex];
            }

            root.rChild = reConstructBinaryTree(rightPre, rightIn);
        }

        return root;
    }

    /**
     * 后续遍历二叉树
     *
     * @param nodeConsumer 遍历过程中对结点的处理函数
     */
    public void PostOrder(Consumer<E> nodeConsumer) {
        postOrder(this.root, nodeConsumer);
    }

    /**
     * 递归 - 后续遍历二叉树
     *
     * @param root         当前根节点
     * @param nodeConsumer 遍历过程中对结点的处理函数
     */
    private void postOrder(Node root, Consumer<E> nodeConsumer) {
        if (root != null) {
            if (root.lChild != null) {
//                nodeConsumer.accept(root.lChild.value);
                postOrder(root.lChild, nodeConsumer);
            }
            if (root.rChild != null) {
//                nodeConsumer.accept(root.rChild.value);
                postOrder(root.rChild, nodeConsumer);
            }
            nodeConsumer.accept(root.value);
        }
    }

    /**
     * 层序遍历
     * @param consumer 遍历过程中对结点的处理函数
     */
    public void levelOrder(Consumer<E> consumer) {
        if (this.root == null) {
            return;
        }
//        层序辅助双端队列
        LinkedList<Node> deQue = new LinkedList<>();
        LinkedList<Node> deQueExchange = new LinkedList<>();
//        初始化
        deQue.add(this.root);
        int level = 1;
//        开始层序遍历
        while (!deQue.isEmpty() || !deQueExchange.isEmpty()) {
            if ((level & 1) == 1) {
                levelOrder(consumer, deQueExchange, deQue);
            } else {
                levelOrder(consumer, deQue, deQueExchange);
            }
            level++;
        }
    }

    /**
     * 辅助层序遍历
     * @param consumer 遍历过程中对结点的处理函数
     * @param deQue 双端队列
     * @param deQueExchange 双端队列(交换)
     */
    private void levelOrder(Consumer<E> consumer, LinkedList<Node> deQue, LinkedList<Node> deQueExchange) {
        while (!deQueExchange.isEmpty()) {
            Node cur = deQueExchange.removeFirst();
            consumer.accept(cur.value);
            if (cur.lChild != null) {
                deQue.add(cur.lChild);
            }
            if (cur.rChild != null) {
                deQue.add(cur.rChild);
            }
        }
    }

    /**
     * 树节点
     */
    private class Node {
        E value;
        Node lChild, rChild;

        public Node(E value) {
            this.value = value;
            this.lChild = null;
            this.rChild = null;
        }
    }

//———————————— 牛 - 客 - 网 ——————————————————————————————————————————————————————————————————————

    /**
     * <a href="https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0?tpId=117&&tqId=37848">
     *     NC136 输出二叉树的右视图</a>
     * @return 树的右视图
     */
    public ArrayList<E> level2() {
        ArrayList<E> ans = new ArrayList<>();
        if (this.root == null) {
            return ans;
        }

        //        层序辅助双端队列
        LinkedList<Node> deQue = new LinkedList<>();
        LinkedList<Node> deQueExchange = new LinkedList<>();
//        初始化
        deQue.add(this.root);
        int level = 1;
        Consumer<E> consumer = e -> {};
//        开始层序遍历
        while (!deQue.isEmpty() || !deQueExchange.isEmpty()) {
            if ((level & 1) == 1) {
                ans.add(deQue.peekLast().value);
                levelOrder(consumer, deQueExchange, deQue);
            } else {
                ans.add(deQueExchange.peekLast().value);
                levelOrder(consumer, deQue, deQueExchange);
            }
            level++;
        }

        return ans;
    }
}
